package huawei;
/*
* @Author: wanghongfucoder
* @Date:   2017-06-27 15:17:00
* @Last Modified by:   wanghongfucoder
* @Last Modified time: 2017-06-27 15:33:29
*/
import java.util.Arrays;
public class BackPack {
	public static void main(String[] args) {
		//背包的重量
		int m = 10;
		//共有几件物品
        int n = 3;
        //物品的重量
        int w[] = {3, 4, 5};
        //物品的价值
        int p[] = {4, 5, 6};
        int c= BackPack_Solution(m, n, w, p);
        System.out.println(c);
	}

	public static  int  BackPack_Solution(int m, int n ,int[] w, int[] p){
		int[][] result=new int[n+1][m+1];
		for (int i=0; i<n+1; i++) {
			result[i][0]=0;
		}
		Arrays.fill(result[0],0);
		for (int i=1;i<n+1 ;i++ ) {
			for (int j=1;j<m+1;j++) {
				if (w[i-1]<=j) {
					result[i][j]=Math.max(result[i-1][j], result[i-1][j-w[i-1]]+p[i-1]);
				}else{
					result[i][j]=result[i-1][j];
				}
			}
		}
		return result[n][m];
	}
}